This volume contains papers from the recursion theory session of the Kazan Workshop on Recursion and Complexity Theory. Recursion theory, the study of computability, is an area of mathematical logic that has traditionally been particularly strong in the United States and the former Soviet Union. This was the first workshop ever to bring together about 50 international experts in recursion theory from the United States, the former Soviet Union and Western Europe.

We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.

We show that the Δ0 2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.

We show that for any computably enumerable set A and any equation image set L, if L is low and equation image, then there is a c.e. splitting equation image such that equation image. In Particular, if L is low and n-c.e., then equation image is n-c.e. and hence there is no low maximal n-c.e. degree.

In this paper we study structural properties of n-c. e. Q-degrees. Two theorems contain results on the distribution of incomparable Q-degrees. In another theorem we prove that every incomplete Q-degree forms a minimal pair in the c. e. degrees with a Q-degree. In a further theorem it is proved that there exists a c. e. Q-degree that is not half of a minimal pair in the c. e. Q-degrees.

We provide three new results about interpolating 2-r.e. or 2-REA degrees between given r.e. degrees: Proposition 1.13. If c h are r.e. , c is low and h is high, then there is an a h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h g there is a properly d-r.e. degree a such that h a g and a is r.e. in h . Theorem 3.1. There is an incomplete nonrecursive r.e. A (...) such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob . The second combines highness with a modified version of the proof strategy of Cooper et al. . The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction. (shrink)

We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.

We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees.

In this work, we study computable families of Turing degrees introduced and first studied by Arslanov and their numberings. We show that there exist finite families of Turing c.e. degrees both those with and without computable principal numberings and that every computable principal numbering of a family of Turing degrees is complete with respect to any element of the family. We also show that every computable family of Turing degrees has a complete with respect to each of its elements (...) computable numbering even if it has no principal numberings. It follows from results by Mal’tsev and Ershov that complete numberings have nice programming tools and computational properties such as Kleene’s recursion theorems, Rice’s theorem, Visser’s ADN theorem, etc. Thus, every computable family of Turing degrees has a computable numbering with these properties. Finally, we prove that the Rogers semilattice of each such non-empty non-singleton family is infinite and is not a lattice. (shrink)

The purpose of the study is to study the main criteria that ensure the development of the regional agricultural industry. Since the development of the subjects of Russia is based on the need to search for new management tools that ensure the long-term development of all sectors of the national economy, state support and state regulation play a special role in the management of the industry. The research focuses on two groups of industry development. The first group includes labor, natural, (...) material, technical and financial resources. The second group includes investment, information, innovation, research and production, and socio-infrastructural resources. However, the second group of resource base factors has a direct impact on the final position of the agricultural sector. As a result, a mechanism for managing the resources of the agricultural sector of the region, based on the growth factors of the agricultural sector, has been identified. (shrink)

According to the Standard Picture of how law works, the content of the law that is created by legal texts such as statutes and constitutional provisions is determined by the meaning of these texts. Most proponents of this picture claim more specifically that the relevant notion of meaning in play is the communicative content of legal texts and that communicative content is itself determined by considerations of the intentions of legal authorities. In recent years, the Standard Picture has become the (...) subject of heated philosophical debate. Focusing on statutes as the paradigmatic type of legal texts, this thesis aims to contribute to this debate in two central ways. First, it argues that the aforementioned ‘intention-based’ versions of the Standard Picture lack convincing responses to three important objections that have been raised by critics. First, they lack an adequate account of how legislative bodies can be reasonably ascribed the intentions that they would need according to such versions. Second, they fail to explain important aspects of legal practice. Third, they provide at best a parochial theory of the content of the law that is generated by statutes. The second contribution is to provide a more sustained defence of the Standard Picture by developing a new ‘commitment-based’ version of this view. This version is based on an alternative theory of communication and claims that communicative content is not determined by considerations of intentions but rather by the commitments that are incurred by means of communicative acts. It is argued that this version can deal with the objections that have been raised by critics and therefore provides a more robust version of the Standard Picture. (shrink)

A frequently discussed question in recent jurisprudential debates concerns the extent to which conversational implicatures can be conveyed reliably in legal language. Roughly, an implicature is a piece of information that a speaker communicates indirectly, that is without making the conveyed information explicit. According to the classical analysis of implicatures, their successful communication depends on a shared expectation of interlocutors to be cooperative in conversation. However, recently some legal theorists have claimed that in legal language implicatures tend to be unreliable (...) because – according to them – communicative cooperation cannot be presumed in legal discourse to the same extent as in ordinary conversations. In this article, I will focus on implicatures in a particular kind of legal discourse, namely judicial opinions, and I will discuss to what extent we should also be sceptical about implicatures in this type of legal discourse. My aim is to suggest that scepticism about the reliability of implicatures in judicial opinions appears implausible once we take evidence into account, i.e. examples of implicatures from judicial opinions. I will argue that the evidence that sceptics provide is not only scarce but inconclusive and present a wealth of implicatures from judicial opinions that are not unreliable. I will conclude that an evidence-based approach casts the sceptical view into doubt and suggest that communicative cooperation is presumed in judicial opinions, as well. (shrink)

We consider so‐called extremal numberings that form the greatest or minimal degrees under the reducibility of all A‐computable numberings of a given family of subsets of, where A is an arbitrary oracle. Such numberings are very common in the literature and they are called universal and minimal A‐computable numberings, respectively. The main question of this paper is when a universal or a minimal A‐computable numbering satisfies the Recursion Theorem (with parameters). First we prove that the Turing degree of a set (...) A is hyperimmune if and only if every universal A‐computable numbering satisfies the Recursion Theorem. Next we prove that any universal A‐computable numbering satisfies the Recursion Theorem with parameters if A computes a non‐computable c.e. set. We also consider the property of precompleteness of universal numberings, which in turn is closely related to the Recursion Theorem. Ershov proved that a numbering is precomplete if and only if it satisfies the Recursion Theorem with parameters for partial computable functions. In this paper, we show that for a given A‐computable numbering, in the general case, the Recursion Theorem with parameters for total computable functions is not equivalent to the precompleteness of the numbering, even if it is universal. Finally we prove that if A is high, then any infinite A‐computable family has a minimal A‐computable numbering that satisfies the Recursion Theorem. (shrink)

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump. We also show that this result does not hold for the limit ordinal. Moreover, we prove that there is no countable structure with the degree spectrum for.

We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.

In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite computable (...) ordinal α. It is known that jump traceability and superlowness coincide on the c.e. sets and we show that for every infinite computable ordinal α, jump traceability with ‐ or ‐bound of a c.e. set A is equivalent to the fact that. Finally, we consider the generalized truth‐table reducibilities and prove that for every (not necessarily the Turing jump of a c.e. set) set A and every limit computable ordinal α, iff. (shrink)

The main question of this article is whether there is a family closed under finite differences (i.e., if A belongs to the family and B=∗A, then B also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman–Wehner families, are deeply studied.

We introduce a hierarchy of sets which can be derived from the integers using countable collections. Such families can be coded into countable algebraic structures preserving their algorithmic properties. We prove that for different finite levels of the hierarchy the corresponding algebraic structures have different classes of possible degree spectra.

We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees.

We study the minimal enumeration degree problem in models of fragments of Peano arithmetic () and prove the following results: in any model M of Σ2 induction, there is a minimal enumeration degree if and only if M is a nonstandard model. Furthermore, any cut in such a model has minimal e-degree. By contrast, this phenomenon fails in the absence of Σ2 induction. In fact, whether every Σ2 cut has minimal e-degree is independent of the Σ2 bounding principle.

Controlled donation after circulatory determination of death (cDCDD) is an important strategy for increasing the pool of eligible organ donors.

Non-therapeutic research with imminently dying patients in intensive care presents complex ethical issues. The vulnerabilities of the imminently dying, together with societal disquiet around death and dying, contribute to an intuition that such research is beyond the legitimate scope of scientific inquiry. Yet excluding imminently dying patients from research hinders the advancement of medical science to the detriment of future patients. Building on existing ethical guidelines for research, we propose a framework for the ethical design and conduct of research involving (...) the imminently dying. To enable rapid translation to practice, we frame the approach in the form of eight ethical questions that researchers and research ethics committees ought to answer prior to conducting any research with this patient population. (1) Does the study hypothesis require the inclusion of imminently dying patients? (2) Are non-therapeutic risks and burdens minimised consistent with sound scientific design? (3) Are the risks of these procedures no more than minimal risk? (4) Are these non-therapeutic risks justified insofar as they are reasonable in relation to the anticipated benefits of the study? (5) Will valid informed consent be obtained from an authorised surrogate decision maker? (6) How will incidental findings be handled? (7) What additional steps are in place to protect families and significant others of research participants? (8) What additional steps are in place to protect clinical staff and researchers? Several ethical challenges hinder research with imminently dying patients. Nonetheless, provided adequate protections are in place, non-therapeutic research with imminently dying patients is ethically justifiable. Applying our framework to an ongoing study, we demonstrate how our question-driven approach is well suited to guiding investigators and research ethics committees. (shrink)

Communication is crucial for us as human beings – much of what we know or believe, we learn through hearing or seeing what others say or express, and arguably part of what makes us human is our desire to communicate our thoughts and feelings to others. A core part of our communicative activity concerns linguistic communication, where we use the words and sentences of natural languages to communicate our ideas. But what exactly is going on in linguistic communication and what (...) is the relationship between what we say and what we think? This entry explores these issues. (shrink)

This article seeks to contribute to the literature on corporate governance with particular focus on state-owned enterprises (SOEs). We put our analysis into the context of Russian SOEs operating in an economy with a high level of the state presence, and investigate the relationship between board characteristics and the dividend policy of SOEs. Specifically, we add to the studies on corporate governance in emerging markets by consideration of professional attorneys, a special category of mandated directors and a unique feature of (...) boards of Russian SOEs. We analysed a panel of 1,226 firm-year observations for 2009-2012, the specific period of incremental innovations in SOEs' governance. Generally, our results support the agency theory and demonstrate that an increase in the proportion of independent directors and professional attorneys and an increase in the dividend payouts occur simultaneously, while the proportion of executives on the board is negatively related to the payout ratio. (shrink)

The purpose of the study is to reveal the factors and features that increase the efficiency of the educational process in universities in modern conditions of digitalization. The article consistently analyzes the features of the processes occurring in the modern digital economy, shows their impact on the effectiveness of the educational environment of the university, and also considers the specific features of digitalization in modern socio-economic conditions. The scientific novelty of the research lies in the theoretical analysis of the ways (...) and means of increasing the efficiency of educational work in the university. Based on the theoretical data of the research, it is possible to create practical and theoretical programs and make possible changes in the educational policy of universities in order to better use digitalization in the educational process. As a result, the article reveals the features of the influence of informatization on the educational environment of the university and ways to improve its efficiency. (shrink)

Reviewed Works:Andrea Sorbi, Complexity, Logic, and Recursion Theory.Klaus Ambos-Spies, Elvira Mayordomo, Resource-Bounded Measure and Randomness.Marat Arslanov, Degree Structures in Local Degree Theory.Jose L. Balcazar, Ricard Gavalda, Montserrat Hermo, Compressibility of Infinite Binary Sequences.S. Barry Cooper, Beyond Godel's Theorem: The Failure to Capture Information Content.Robert A. Di Paola, Franco Montagna, Progressions of Theories of Bounded Arithmetic.Rodney G. Downey, On Presentations of Algebraic Structures.Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet, Witness-Isomorphic Reductions and Local Search.William Gasarch, Carl H. Smith, A Survey of (...) Inductive Inference with an Emphasis on Queries.Andre Nies, A Uniformity of Degree Structures.Piergiorgio Odifreddi, Short Course on Logic, Algebra, and Topology.Andrea Sorbi, The Enumeration Degrees of the $\sigma^0_2$ Sets.Peter van Emde Boas, The Convenience of Tilings. (shrink)

We discuss the effectivity of Arslanov’s completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the effectivity of another extension of the recursion theorem, namely Visser’s ADN theorem, as well as that of a joint generalization of the ADN theorem and Arslanov’s completeness criterion.